A web graph is a representation of the link structure of the World Wide Web (hereinafter the “web”). The graph can be encoded in a variety of data structures, including a matrix. For example, the links between documents in the web can be encoded in the rows and columns of the matrix. As the web contains billions of documents, even a modestly comprehensive matrix representation of the web will be sparse and very large.
The web graph can be used to perform a variety of computations. One example is Page Rank. Due to the size and other properties of the web graph, computations can be very resource intensive. There thus exists a continuing need to be able to process the web graph efficiently.